import java.util.*;

/**
* @description: 周赛311 t3
* @author hewei
* @date 2022/9/18 10:40
* @version 1.0
*/

public class ReverseOddLevels {

    public TreeNode reverseOddLevels1(TreeNode root) {
        Deque<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int count = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            Deque<Integer> list = new LinkedList<>();
            Stack<TreeNode> stack = new Stack<>();
            while (size-- > 0) {
                TreeNode poll = queue.poll();
                if (poll.left != null) queue.add(poll.left);
                if (poll.right != null) queue.add(poll.right);
                if (count % 2 == 1) {
                    stack.push(poll);
                    list.add(poll.val);
                }
            }
            while (!stack.isEmpty()) {
                stack.pop().val = list.poll();
            }
            ++count;
        }
        return root;
    }

    public TreeNode reverseOddLevels(TreeNode root) {
        dfs(root.left, root.right, 1);
        return root;
    }

    public void dfs(TreeNode l, TreeNode r, int level) {
        if (l == null) return;
        if (level % 2 == 0) {
            int temp = l.val;
            l.val = r.val;
            r.val = temp;
        }
        dfs(l.left, r.right, level + 1);
        dfs(l.right, r.left, level + 1);
    }
}
